#include<iostream>
#include<string>
#include<vector>
using namespace std;
//https://leetcode-cn.com/problems/implement-strstr/solution/zhe-ke-neng-shi-quan-wang-zui-xi-de-kmp-8zl57/
//https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/


// /******************************** KMP算法 ****************************/

// /* 通过计算返回子串T的next数组。 */
// void get_next(string T, int *next) 
// {
// 	    int i,j;
//   	i=0; // 后缀末尾
//   	j=-1; // 前缀末尾
//   	next[0]=-1;
//   	while (i<T.size())  /* 此处T[0]表示串T的长度 */
//  	{
//      // 匹配的情况
//     	if(j==-1 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
// 		{
//       		++i;  
// 			++j;  
// 			next[i] = j;
//     	} 
//      // 不匹配的情况下回退
// 		else 
// 			j= next[j];	/* 若字符不相同，则j值回溯 */
//   	}
// }

// /* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
// /*  T非空，1≤pos≤StrLength(S)。 */
// int Index_KMP(string S, string T, int pos) 
// {
// 	int i = pos;		/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
// 	int j = 0;			/* j用于子串T中当前位置下标值 */
// 	int next[255];		/* 定义一next数组 */
// 	get_next(T, next);	/* 对串T作分析，得到next数组 */
// 	while (i < S.size() && j < T.size()) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
// 	{
// 		if (j==-1 || S[i] == T[j]) 	/* 两字母相等则继续，与朴素算法增加了j=0判断 */
//       	{
//          	++i;
//          	++j; 
//       	} 
//       	else 			/* 指针后退重新开始匹配 */
//       	 	j = next[j];/* j退回合适的位置，i值不变 */
// 	}
// 	if (j >= T.size()) 
// 		return i-T.size();
// 	else 
// 		return 0;
// }
// /****************************************************************/


class Solution {
public:
    int strStr(string S, string T) {
        int i = 0;		/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
        int j = 0;			/* j用于子串T中当前位置下标值 */
        int Slen = S.size();
        int Tlen = T.size();
        int next[Tlen+1];		/* 定义一next数组 */
        get_next(T, next);	/* 对串T作分析，得到next数组 */

        while (i < Slen && j < Tlen) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
        {
            if (j==-1 || S[i] == T[j]) 	/* 两字母相等则继续，与朴素算法增加了j=0判断 */
            {
                ++i;
                ++j;
            } 
            else 			/* 指针后退重新开始匹配 */
            {
                j = next[j];/* j退回合适的位置，i值不变 */
                // cout << j << endl;
            }
        }

        if (j >= T.size()) 
            return i-T.size();
        else 
            return -1;
    }
    // 有问题！！
    void get_next(string T, int *next)  // 经过验证没问题，next[0] = -1表示没有匹配的
    {
        int i,j;
        i=0;
        j=-1;  
        next[0]=-1; // 无公共前后缀
        while (i<T.size())  /* 表示串T的长度 */
        {
            if(j==-1 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
            {
                ++i;  
                ++j;  
                next[i] = j;
            } 
            else 
                j= next[j];	/* 若字符不相同，则j值回溯 */
        }
    }

};


int main(int argc, char** argv) {
    Solution solu = Solution();
    // string haystack = "hello";
    // string needle = "ll";
    // string needle = "bcbcbea";
    string haystack = "aaaaa";
    string needle = "bba";
    // string haystack = "aaaaa";
    // string needle = "";

    
    int firstplace =  solu.strStr(haystack, needle);
    cout << firstplace << endl;

    return 0;
}
